package algorithm.sort;

import java.util.Arrays;

/**
 * @ClassName : data_structure.TestSort.QuickSort
 * @Description : 类描述
 * Created by cyd on 2021-02-15 21:43:29
 */
public class QuickSort {

    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSort(arr, 0, arr.length - 1);
    }

    // 分治递归
    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    // 分区并操作一次，返回分界点
    //  分界点左侧的数组，每个元素都比右侧的小
    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        // 用于交换的索引
        int index = pivot + 1;

        // 循环是为了将所有的元素，与基准点元素对比一边
        for (int i = index; i <= right; i++) {
            // 一旦发现小于基准点的，就挨个换到基准点后面
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                // 索引后移，为交换腾出位置
                index++;
            }
        }
        // 将基准点处元素，和基准点后面换过来的最后一个元素交换位置
        // 此时该元素左边一定小于基准点右边
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    // 交换的方法
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) throws Exception {
        int[] ints = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 0, -1};
        QuickSort quickSort = new QuickSort();
        int[] sort = quickSort.sort(ints);
        System.out.println(Arrays.toString(ints));
        System.out.println(Arrays.toString(sort));

    }
}
